public class 反转链表II {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 引入一个头指针
        ListNode t = new ListNode();
        t.next = head;
        // 找到 left 前一个点, 找到 left , 找到 right , 找到 right 下一个点
        ListNode preL = null;
        ListNode l = t;
        int cnt = right - left;
        // 找左
        while(left-- > 0) {
            preL = l;
            l = preL.next;
        }
        ListNode rNext = t;
        while(right-- > 0) {
            rNext = rNext.next;
        }
        rNext = rNext.next;
        // 反转内部链表
        ListNode haedT = new ListNode(-555);
        ListNode cur = l;
        while(cnt-- > 0) {
            ListNode next = cur.next;
            cur.next = haedT.next;
            haedT.next = cur;
            cur = next;
        }
        // 最后一个元素头插
        cur.next = haedT.next;
        haedT.next = cur;
        // 修改头尾
        l.next = rNext;
        preL.next = haedT.next;
        return t.next;
    }



    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
        }

}
